{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "80795cfd-5780-4eba-a64e-49efefa998b9",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree\n",
    "\n",
    "\n",
    "Success.\n",
    "\n",
    "___\n",
    "\n",
    "\n",
    "```python\n",
    "class Solution:\n",
    "    def get_nodes_separated_by_levels(self, root):\n",
    "        if root == None:\n",
    "            return []\n",
    "        \n",
    "        a_list = [root]\n",
    "        b_list = []\n",
    "        switch_flag = 0\n",
    "        level_list = []\n",
    "\n",
    "        while True:\n",
    "            if len(a_list) == 0 and len(b_list) == 0:\n",
    "                break\n",
    "            \n",
    "            if switch_flag == 0:\n",
    "                for node in a_list:\n",
    "                    if node.left:\n",
    "                        b_list.append(node.left)\n",
    "                    if node.right:\n",
    "                        b_list.append(node.right)\n",
    "                level_list.append([n for n in a_list])\n",
    "                a_list = []\n",
    "                switch_flag = 1\n",
    "            else:\n",
    "                for node in b_list:\n",
    "                    if node.left:\n",
    "                        a_list.append(node.left)\n",
    "                    if node.right:\n",
    "                        a_list.append(node.right)\n",
    "                level_list.append([n for n in b_list])\n",
    "                b_list = []\n",
    "                switch_flag = 0\n",
    "        \n",
    "        return level_list\n",
    "\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        #2023/01/09 08:44\n",
    "        self.answer = None\n",
    "        self.node_list = []\n",
    "\n",
    "        def travel(node):\n",
    "            if self.answer != None:\n",
    "                return\n",
    "\n",
    "            if node:\n",
    "                self.node_list.append(node)\n",
    "                \n",
    "                value_list = [node.val]\n",
    "                if node.left != None:\n",
    "                    value_list.append(node.left.val)\n",
    "                if node.right != None:\n",
    "                    value_list.append(node.right.val)\n",
    "                #print(value_list)\n",
    "                if p.val in value_list and q.val in value_list:\n",
    "                    self.answer = node\n",
    "                    return\n",
    "\n",
    "                travel(node.left)\n",
    "                travel(node.right)\n",
    "        travel(root)\n",
    "\n",
    "        def check_the_node(node):\n",
    "            value_list = []\n",
    "            \n",
    "            def travel_x(node_):\n",
    "                if node_:\n",
    "                    value_list.append(node_.val)\n",
    "                    if node_.left:\n",
    "                        travel_x(node_.left)\n",
    "                    if node_.right:\n",
    "                        travel_x(node_.right)\n",
    "            travel_x(node)\n",
    "\n",
    "            if p.val in value_list and q.val in value_list:\n",
    "                self.answer = node\n",
    "        \n",
    "        if self.answer != None:\n",
    "            return self.answer\n",
    "        else:\n",
    "            self.node_list = []\n",
    "            for sub_list in self.get_nodes_separated_by_levels(root):\n",
    "                self.node_list += sub_list\n",
    "            for node in self.node_list:\n",
    "                #print(node.val)\n",
    "                check_the_node(node)\n",
    "            if self.answer == None:\n",
    "                return root\n",
    "            else:\n",
    "                return self.answer\n",
    "        #2023/01/09 11:18\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97700a8a-89a3-4308-91b0-cdd593476d83",
   "metadata": {},
   "source": [
    "# Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4194a090-1094-4d98-b964-39eb04eb0a75",
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "    def __repr__(self):\n",
    "        return 'TreeNode({})'.format(self.val)\n",
    "    \n",
    "def deserialize(string):\n",
    "    if string == '{}':\n",
    "        return None\n",
    "    nodes = [None if val == 'null' else TreeNode(int(val))\n",
    "             for val in string.strip('[]{}').split(',')]\n",
    "    kids = nodes[::-1]\n",
    "    root = kids.pop()\n",
    "    for node in nodes:\n",
    "        if node:\n",
    "            if kids: node.left  = kids.pop()\n",
    "            if kids: node.right = kids.pop()\n",
    "    return root\n",
    "\n",
    "def drawtree(root):\n",
    "    def height(root):\n",
    "        return 1 + max(height(root.left), height(root.right)) if root else -1\n",
    "    def jumpto(x, y):\n",
    "        t.penup()\n",
    "        t.goto(x, y)\n",
    "        t.pendown()\n",
    "    def draw(node, x, y, dx):\n",
    "        if node:\n",
    "            t.goto(x, y)\n",
    "            jumpto(x, y-20)\n",
    "            t.write(node.val, align='center', font=('Arial', 12, 'normal'))\n",
    "            draw(node.left, x-dx, y-60, dx/2)\n",
    "            jumpto(x, y-20)\n",
    "            draw(node.right, x+dx, y-60, dx/2)\n",
    "    import turtle\n",
    "    t = turtle.Turtle()\n",
    "    t.speed(0); turtle.delay(0)\n",
    "    h = height(root)\n",
    "    jumpto(0, 30*h)\n",
    "    draw(root, 0, 30*h, 40*h)\n",
    "    t.hideturtle()\n",
    "    turtle.mainloop()\n",
    "    \n",
    "#drawtree(deserialize('[2,1,3,0,7,9,1,2,null,1,0,null,null,8,8,null,null,null,null,7]'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7b85349a-7091-4fd3-954c-c28521021469",
   "metadata": {},
   "outputs": [],
   "source": [
    "drawtree(deserialize('[5,3,6,1,4,null,null,null,2]'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ae238433-3920-4a06-8afd-5344beaf59ab",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}